HDU 4122 Alice's mooncake shop(贪心、RMQ)

题意:

$给定N\le 2500个订单,升序排列,保证合法$
$现在有个店开M\le 10^5小时,每小时做月饼的价格都不一样,不考虑做月饼的时间$
$每个月饼的保质期是t\le 10^5小时,每小时的花费为s\le 200$
$订单可以现做现卖,问如何制作才能满足所有订单,并使得总花费最小$
$求这个花费$

分析:

$首先先解析日期都成小时$
$对于i小时的订单,显然应该取[i-t+1, i]的最小的那个花费$
$为了方便处理,假设都在最后一天买,显然某一天的花费应该a_i+(m-i)\times s$
$之后取min\{cost[i-t+1, i]\},再减去多算的(m-i)\times s$
$然后就做完了$
$时间复杂度O(nlogm+m)$
$妈蛋,我样处理日期要考虑重复的情况,赛上T到死了。。。while与if的一字之差$

代码:

//
//  Created by TaoSama on 2016-05-02
//  Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
#include <tuple>
#include <cassert>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 2e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, m;
int t, s;
struct Order {
    int y, m, d, h;
    int id;
    void read() {
        scanf("%d%d%d%d", &d, &y, &h, &r);
    }
    void see() {
        printf("(%d, %d, %d, %d)\n", y, m, d, h);
    }
    int r;
} o[2505];

void RE() {
    printf("%d\n", *((int*)0));
}

typedef long long LL;

LL a[N];

struct SparseTable {
    int n;
    LL dp[20][N];
    void init(int _n, LL* a) {
        n = _n;
        for(int i = 1; i <= n; ++i) dp[0][i] = a[i];
        for(int i = 1; (1 << i) <= n; ++i)
            for(int j = 1; j + (1 << i) - 1 <= n; ++j)
                dp[i][j] = min(dp[i - 1][j],
                               dp[i - 1][j + (1 << i - 1)]);
    }
    LL RMQ(int l, int r) {
        int k = 31 - __builtin_clz(r - l + 1);
        return min(dp[k][l], dp[k][r - (1 << k) + 1]);
    }
} st;


char mm[][10] = {"", "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
int mdays[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeap(int y) {
    return y % 4 == 0 && y % 100 || y % 400 == 0;
}

void go(int& y, int& m, int& d, int& h) {
    ++h;
    if(h >= 24) h = 0, ++d;
    int cur = mdays[m];
    if(m == 2 && isLeap(y)) ++cur;
    if(d > cur) d -= cur, ++m;
    if(m > 12) m -= 12, ++y;
}

int getTime(int m, int day, int year, int h) {
    int res = 0;
    for(int i = 2000; i < year; i++) {
        if(isLeap(i))res += 366 * 24;
        else res += 365 * 24;
    }
    for(int i = 1; i < m; i++) {
        res += mdays[i] * 24;
        if(isLeap(year) && i == 2)res += 24;
    }
    for(int i = 1; i < day; i++)res += 24;
    res += h + 1;
    return res;
}

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);


    while(scanf("%d%d", &n, &m) == 2 && (n || m)) {
        for(int i = 1; i <= n; ++i) {
            char mon[10]; scanf("%s", mon);
            o[i].read();
            for(int j = 1; j <= 12; ++j) {
                if(!strcmp(mm[j], mon)) {
                    o[i].m = j;
                    break;
                }
            }

        }
        scanf("%d%d", &t, &s);

        int Y = 2000, M = 1, D = 1, H = 0;
        for(int j = 1, i = 1; ; ++j) {
//          o[i].see();
            while(make_tuple(Y, M, D, H) ==
                    make_tuple(o[i].y, o[i].m, o[i].d, o[i].h)) {
                o[i].id = j;
//                printf("%d = %d\n", i, j);
                ++i;
            }
            if(i == n + 1) break;
            go(Y, M, D, H);
        }


        for(int i = 1; i <= m; ++i) {
            scanf("%I64d", a + i);
            a[i] += 1LL * (m - i) * s;
        }
        st.init(m, a);

        LL ans = 0;
        for(int i = 1; i <= n; ++i) {
            int d = o[i].id;
            LL cur = st.RMQ(max(1, d - t + 1), d);
            cur -= 1LL * (m - d) * s;
            ans += cur * o[i].r;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}